#include <algorithm>
#include <cctype>
#include <cstdio>

const int N = 50005;
int n, m, cnt, rt[N << 2], a[N];

struct bstNode {
  int cnt, val, ch[2], fa, siz;
} tr[N << 5];

inline int read() {
  int ch = getchar(), res = 0;
  bool flag = false;
  while (!isdigit(ch)) {
    if (ch == '-') flag = true;
    ch = getchar();
  }
  while (isdigit(ch)) res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
  return flag ? -res : res;
}

inline bool iden(int x) { return tr[tr[x].fa].ch[1] == x; }

inline void update(int x) {
  if (x) {
    tr[x].siz = tr[x].cnt;
    if (tr[x].ch[0]) tr[x].siz += tr[tr[x].ch[0]].siz;
    if (tr[x].ch[1]) tr[x].siz += tr[tr[x].ch[1]].siz;
  }
}

inline void connect(int x, int y, bool typ) {
  if (x) tr[x].fa = y;
  if (y) tr[y].ch[typ] = x;
}

inline void rotate(int x) {
  int fa = tr[x].fa, ffa = tr[fa].fa;
  bool i_fa = iden(x), i_ffa = iden(fa);
  connect(x, ffa, i_ffa);
  connect(tr[x].ch[!i_fa], fa, i_fa);
  connect(fa, x, !i_fa);
  update(fa), update(x);
}

inline void splay(int x, int tar, int rootid) {
  for (int fa; (fa = tr[x].fa) != tar; rotate(x))
    if (tr[fa].fa != tar) rotate(iden(x) == iden(fa) ? fa : x);
  if (!tar) rt[rootid] = x;
}

inline void insert(int v, int rootid) {
  if (!rt[rootid]) {
    ++cnt;
    tr[cnt].fa = tr[cnt].ch[0] = tr[cnt].ch[1] = 0;
    tr[cnt].siz = tr[cnt].cnt = 1;
    tr[cnt].val = v;
    rt[rootid] = cnt;
    return;
  }
  int cur = rt[rootid], fa = 0;
  while (true) {
    if (tr[cur].val == v) {
      tr[cur].cnt++;
      update(cur);
      update(fa);
      splay(cur, 0, rootid);
      return;
    } else if (v < tr[cur].val)
      fa = cur, cur = tr[cur].ch[0];
    else
      fa = cur, cur = tr[cur].ch[1];
    if (!cur) {
      ++cnt;
      tr[cnt].fa = fa, tr[cnt].val = v, tr[cnt].ch[0] = tr[cnt].ch[1] = 0;
      tr[cnt].siz = tr[cnt].cnt = 1;
      tr[fa].ch[v > tr[fa].val] = cnt;
      rt[rootid] = cnt;
      update(fa);
      splay(cnt, 0, rootid);
      return;
    }
  }
}

inline int rank(int k, int rootid) {
  int cur = rt[rootid], res = 0;
  while (cur) {
    if (k < tr[cur].val) {
      cur = tr[cur].ch[0];
    } else {
      res += tr[tr[cur].ch[0]].siz;
      if (k == tr[cur].val) {
        splay(cur, 0, rootid);
        return res;
      } else {
        res += tr[cur].cnt;
        cur = tr[cur].ch[1];
      }
    }
  }
  if (cur) splay(cur, 0, rootid);
  return res;
}

inline int find(int k, int rootid) {
  int cur = rt[rootid];
  while (cur) {
    if (k <= tr[tr[cur].ch[0]].siz) cur = tr[cur].ch[0];
    else if (tr[tr[cur].ch[0]].siz < k &&
             k <= tr[tr[cur].ch[0]].siz + tr[cur].cnt) {
      break;
    } else {
      k -= tr[tr[cur].ch[0]].siz + tr[cur].cnt;
      cur = tr[cur].ch[1];
    }
  }
  if (cur) splay(cur, 0, rootid);
  return tr[cur].val;
}

inline int upper(int k, int rootid) {
  int cur = rt[rootid], res = 2147483647;
  while (cur) {
    if (tr[cur].val > k && tr[cur].val < res) res = tr[cur].val;
    if (k <= tr[cur].val) {
      cur = tr[cur].ch[0];
    } else {
      cur = tr[cur].ch[1];
    }
  }
  return res;
}

inline int lower(int k, int rootid) {
  int cur = rt[rootid], res = -2147483647;
  while (cur) {
    if (tr[cur].val < k && tr[cur].val > res) res = tr[cur].val;
    if (k <= tr[cur].val) {
      cur = tr[cur].ch[0];
    } else {
      cur = tr[cur].ch[1];
    }
  }
  return res;
}

inline void dele(int v, int rootid) {
  rank(v, rootid);
  int cur = rt[rootid];
  if (tr[rt[rootid]].cnt > 1) {
    tr[rt[rootid]].cnt--;
    update(rt[rootid]);
    return;
  }
  if (!tr[cur].ch[0] && !tr[cur].ch[1]) {
    rt[rootid] = 0;
    return;
  }
  if (!tr[cur].ch[0]) {
    rt[rootid] = tr[cur].ch[1];
    tr[tr[cur].ch[1]].fa = 0;
    return;
  }
  if (!tr[cur].ch[1]) {
    rt[rootid] = tr[cur].ch[0];
    tr[tr[cur].ch[0]].fa = 0;
    return;
  }
  int lef = tr[rt[rootid]].ch[0], org = rt[rootid];
  while (tr[lef].ch[1]) lef = tr[lef].ch[1];
  splay(lef, 0, rootid);
  connect(tr[org].ch[1], rt[rootid], 1);
  update(rt[rootid]);
}

void build(int x, int l, int r) {
  for (int i = l; i <= r; ++i) { insert(a[i], x); }
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
}

void modify(int x, int l, int r, int pos, int v) {
  dele(a[pos], x);
  insert(v, x);
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (pos <= mid) modify(x << 1, l, mid, pos, v);
  if (mid < pos) modify(x << 1 | 1, mid + 1, r, pos, v);
}

int queryRank(int x, int l, int r, int L, int R, int k) {
  if (L <= l && r <= R) { return rank(k, x); }
  int mid = (l + r) >> 1, res = 0;
  if (L <= mid) res += queryRank(x << 1, l, mid, L, R, k);
  if (mid < R) res += queryRank(x << 1 | 1, mid + 1, r, L, R, k);
  return res;
}

inline int queryVal(int l, int r, int k) {
  int L = 0, R = 1e8, mid;
  while (L < R) {
    mid = (L + R + 1) >> 1;
    if (queryRank(1, 1, n, l, r, mid) < k) {
      L = mid;
    } else
      R = mid - 1;
  }
  return R;
}

int queryLower(int x, int l, int r, int L, int R, int k) {
  if (L <= l && r <= R) return lower(k, x);
  int mid = (l + r) >> 1, res = -2147483647;
  if (L <= mid) res = std::max(res, queryLower(x << 1, l, mid, L, R, k));
  if (mid < R) res = std::max(res, queryLower(x << 1 | 1, mid + 1, r, L, R, k));
  return res;
}

int queryUpper(int x, int l, int r, int L, int R, int k) {
  if (L <= l && r <= R) return upper(k, x);
  int mid = (l + r) >> 1, res = 2147483647;
  if (L <= mid) res = std::min(res, queryUpper(x << 1, l, mid, L, R, k));
  if (mid < R) res = std::min(res, queryUpper(x << 1 | 1, mid + 1, r, L, R, k));
  return res;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("TreeInTree.in", "r", stdin);
  freopen("TreeInTree.out", "w", stdout);
#endif
#endif

  n = read(), m = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  build(1, 1, n);
  int opt, l, r, x, y, k;
  while (m--) {
    opt = read();
    switch (opt) {
      case 1:
        l = read(), r = read(), k = read();
        printf("%d\n", queryRank(1, 1, n, l, r, k) + 1);
        break;
      case 2:
        l = read(), r = read(), k = read();
        printf("%d\n", queryVal(l, r, k));
        break;
      case 3:
        x = read(), y = read();
        modify(1, 1, n, x, y);
        a[x] = y;
        break;
      case 4:
        l = read(), r = read(), k = read();
        printf("%d\n", queryLower(1, 1, n, l, r, k));
        break;
      case 5:
        l = read(), r = read(), k = read();
        printf("%d\n", queryUpper(1, 1, n, l, r, k));
        break;
    }
  }
  return 0;
}